#define _CRT_SECURE_NO_WARNINGS 1

#include "Sort.h"
#include "Stack.h"

void printArr(int* arr, int sz)
{
	for (int i = 0;i <= sz - 1;i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void InsertSort(int* arr, int sz)//1.直接插入排序
{
	assert(arr != NULL);
	for (int i = 0;i <= sz - 2;i++)
	{
		int end = i;//把数组第一个元素当作有序，像打扑克牌摸牌排序一样
		int x = arr[end + 1];
		//x已经保存了a[end + 1] 所以后面再覆盖也可以 因此end只能落在sz-2
		while (end >= 0)
		{
			if (arr[end] > x)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = x;
	}
}

void ShellSort(int* arr, int sz)//2.希尔排序
{
	int gap = sz;
	//多次预排序(gap > 1)+直接插入排序(gap == 1)
	while (gap > 1)//gap进去以后才除所以大于1就行
	{
		//两种取gap的方法：
		//gap = gap / 2;//一次跳一半
		gap = gap / 3 + 1;
		//加一是为了保证最后一次gap小于3的时候
		//能够有gap等于1来表示直接插入排序
		//多组同时搞：
		for (int i = 0; i < sz - gap; i++)
		{
			int end = i;
			int x = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > x)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = x;
		}
	}
}

void SelectSort(int* arr, int sz)//3.选择排序
{
	int begin = 0;
	int end = sz - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = end;
		int i = 0;
		for (i = begin;i <= end;i++)
		{
			//选出[begin,end]中最大和最小的
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		//int arr[] = { 1,6,5,4,7,8,9,2,0,3 };

		Swap(&arr[begin], &arr[mini]);
		//这里需要考虑第一个值放最大值的情况，如果第一个值为最大值,此时最大值位置被移动
		if (begin == maxi)
		{
			maxi = mini;//最大的值被换到了mini的位置，更新最大值的位置
		}
		Swap(&arr[end], & arr[maxi]);
		begin++;
		end--;
	}
}

void justDown(int* arr, int sz, int father_idx)//大堆下调
{
	int child_idx = father_idx * 2 + 1; // 计算出左孩子的值（默认认为左孩子大）
	while (child_idx < sz) // 最坏情況：调到叶子（child_idx >= 数组范围时必然已经调到叶子）
	{
		if ((child_idx + 1 < sz) && (arr[child_idx + 1] > arr[child_idx]))
		{   // 如果右孩子存在且右孩子比左孩子大
			child_idx = child_idx + 1;// 让其代表右孩子
		}
		if (arr[child_idx] > arr[father_idx])//如果孩子的值大于父亲的值（不符合大堆的性质）
		{
			Swap(&arr[child_idx], &arr[father_idx]);
			father_idx = child_idx;          // 更新下标往下走
			child_idx = father_idx * 2 + 1;  // 计算出该节点路线的新父亲
		}
		else // 如果孩子的值小于父亲的值（符合大堆的性质）
		{
			break;
		}
	}
}

void HeapSort(int* arr, int sz)//4.堆排序
{
	//创建大堆，选出最大的数，时间：O(N)
	int father = ((sz - 1) - 1) / 2;  // 计算出最后一个叶子节点的父亲
	while (father >= 0)
	{
		justDown(arr, sz, father);
		father--;
	}

	//交换后调堆  时间：O(N * logN)
	int end = sz - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		justDown(arr, end, 0);
		end--;
	}
}

void BubbleSort(int* arr, int sz)//5.冒泡排序
{
	int i = 0;
	int j = 0;
	for (i = 0;i < sz - 1;i++)
	{
		int flag = 1;
		for (j = 0;j < sz - 1 - i;j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
			}
			flag = 0;
		}
		if (flag)
		{
			break;
		}
	}
}

int GetMidIndex(int* arr, int left, int right)//三数取中
{
	int mid = left + (right - left) / 2;
	if (arr[mid] > arr[left])
	{
		if (arr[mid] < arr[right])
			return mid;
		else if (arr[left] > arr[right])
			return left;
		else
			return right;
	}
	else
	{
		if (arr[mid] > arr[right])
			return mid;
		else if (arr[left] > arr[right])
			return right;
		else
			return left;
	}
}

int PartSort1(int* arr, int left, int right)//Hoare法快速排序
{
	int midIndex = GetMidIndex(arr, left, right);//加上三数取中
	Swap(&arr[left], &arr[midIndex]);//把中间元素和最左边元素换了就行

	int keyi = left;
	while (left < right)
	{
		//右边先走 找小 控制不要错开不要越界
		while (left < right && arr[right] >= arr[keyi])
		{
			--right;
		}
		//左边再走 找大 控制不要错开不要越界
		while (left < right && arr[left] <= arr[keyi])
		{
			++left;
		}
		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[left], &arr[keyi]);//交换相遇的地方和关键字的位置
	return left;//返回关键字的位置
}

int PartSort2(int* arr, int left, int right)//挖坑法快速排序
{
	int midIndex = GetMidIndex(arr, left, right);//加上三数取中
	int pit = midIndex;
	int keyi = pit;
	while (left < right)
	{
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}
		arr[pit] = arr[right];
		pit = right;
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		arr[pit] = arr[left];
		pit = left;
	}
	arr[pit] = arr[keyi];
	return pit;
}

int PartSort3(int* arr, int left, int right)//前后指针法快速排序
{
	int midIndex = GetMidIndex(arr, left, right);//加上三数取中
	Swap(&arr[left], &arr[midIndex]);//把中间元素和最左边元素换了就行

	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur <= right)
	{
		while (cur <= right && arr[cur] >= arr[keyi])
		{
			cur++;
		}
		if (cur <= right)
		{
			prev++;
			Swap(&arr[cur], &arr[prev]);
			cur++;
		}
		if (arr[cur] < arr[keyi] && ++prev != cur)//反正都要cur++，注意这里prev已经++了
		{
			Swap(&arr[cur], &arr[prev]);
		}
		cur++;//前面注释的优化
	}
	Swap(&arr[prev], &arr[keyi]);
	return prev;
}

void QuickSort(int* arr, int left, int right)//6.快速排序递归版
{
	if (left >= right)
	{
		return;
	}
	if (right - left + 1 < 19)//可以自己取，官方是十几
	{
		InsertSort(arr + left, right - left + 1);
	}
	else
	{
		//int keyi = PartSort1(arr, left, right);
        int keyi = PartSort2(arr, left, right);
		//int keyi = PartSort3(arr, left, right);
		QuickSort(arr, left, keyi - 1);
		QuickSort(arr, keyi + 1, right);
	}
}

void QuickSortNonR(int* arr, int left, int right)//6.快速排序非递归版
{
	Stack st;
	StackInit(&st);
	StackPush(&st, right);//为了更类似上面的递归就先入右
	StackPush(&st, left);

	while (!StackEmpty(&st))
	{
		int begin = StackTop(&st);
		StackPop(&st);

		int end = StackTop(&st);
		StackPop(&st);

		int keyi = PartSort3(arr, begin, end);
	    
		//区间被成两部分了 [begin,keyi-1]    [keyi+1,end]
		if (keyi + 1 < end)//先处理右
		{
			StackPush(&st, end);
			StackPush(&st, keyi + 1);
		}
		if(begin < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, begin);
		}
	}
	StackDestroy(&st);
}

void _MergeSort(int* arr, int left, int right, int* tmp)//归并排序递归版的子函数
{
	if (left >= right)//归并结束条件：当只有一个数据或是序列不存在时（认为有序）
	{
		return;
	}

	int mid = left + (right - left) / 2;
	//[left,mid]   [mid+1,right]  分治递归，让子区间有序
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);

	//将两段子区间进行归并，归并结果放在tmp中
	int left1 = left, right1 = mid;
	int left2 = mid + 1, right2 = right;
	int i = left;
	while (left1 <= right1 && left2 <= right2)
	{
		//将较小的数据优先放入tmp，放入后++
		if (arr[left1] < arr[left2])
		{
			tmp[i++] = arr[left1++];
		}
		else
		{
			tmp[i++] = arr[left2++];
		}
	}
	//当遍历完其中一个区间，将另一个区间剩余的数据直接放到tmp的后面
	while (left1 <= right1)//有一个while循环条件肯定不满足，不用管
	{
		tmp[i++] = arr[left1++];
	}
	while (left2 <= right2)
	{
		tmp[i++] = arr[left2++];
	}

	//归并完后，拷贝回原数组
	//for (int j = left; j <= right; j++)
	//{
	//	arr[j] = tmp[j];
	//}
	memcpy(arr + left, tmp + left, (right - left + 1) * sizeof(int));
}

void MergeSort(int* arr, int sz)//7.归并排序递归版
{
	int* tmp = (int*)malloc(sizeof(int) * sz);//申请一个与原数组大小相同的空间
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	_MergeSort(arr, 0, sz - 1, tmp);//函数前加_用来表示其子函数，常用来递归

	free(tmp);
	tmp = NULL;
}

void MergeSortNonR(int* arr, int sz)//7.归并排序非递归版
{
	int* tmp = (int*)malloc(sizeof(int) * sz);
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	memset(tmp, 0, sizeof(int) * sz);

	int gap = 1;
	while (gap < sz)
	{
		for (int i = 0; i < sz; i += 2 * gap)//控制每次参与合并的元素个数
		{
			// [i, i + gap - 1]  [i + gap, i + 2 * gap - 1]
			int left1 = i, right1 = i + gap - 1;
			int left2 = i + gap, right2 = i + 2 * gap - 1;
			// 防止越界核心思想：right1、left2、right2都有可能越界
			if (right1 >= sz || left2 >= sz)// right1越界 或者 left2 越界都不需要归并
			{
				break;
			}
			else if (right2 >= sz)// right2 越界，需要归并，修正right2
			{
				right2 = sz - 1;
			}

			int n = right2 - left1 + 1;//记录要拷贝的个数
			int j = left1;
			while (left1 <= right1 && left2 <= right2)
			{
				if (arr[left1] <= arr[left2])//加个等于就是稳定的（后面会讲稳定性）
				{
					tmp[j++] = arr[left1++];
				}
				else
				{
					tmp[j++] = arr[left2++];
				}
			}
			while (left1 <= right1)
			{
				tmp[j++] = arr[left1++];
			}
			while (left2 <= right2)
			{
				tmp[j++] = arr[left2++];
			}
			// 把归并小区间拷贝回原数组
			//for (int k = i; k <= right2; k++)
			//{
			//	arr[k] = tmp[k];
			//}
			memcpy(arr + i, tmp + i, sizeof(int) * n);
		}
		gap *= 2;
	}
	free(tmp);
	tmp = NULL;
}

void CountSort(int* arr, int sz)//8.计数排序
{
	int min = arr[0];
	int max = arr[0];
	for (int i = 0; i < sz; i++)//找出数组中的最大值和最小值,为了后面开辟数组
	{
		if (arr[i] < min)
		{
			min = arr[i];
		}
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}
	int range = max - min + 1;//min和max之间的自然数个数（包括min和max本身）
	int* count = (int*)calloc(range, sizeof(int));//开辟可储存range个整型的内存空间，并将内存空间置0
	if (count == NULL)
	{
		printf("calloc fail\n");
		exit(-1);
	}

	for (int i = 0; i < sz; i++)//统计相同元素出现次数（相对映射）
	{
		count[arr[i] - min]++;
	}

	int i = 0;
	for (int j = 0; j < range; j++)//根据统计结果将序列回收到原来的数组中
	{
		while (count[j]--)
		{
			arr[i++] = j + min;
		}
	}
	free(count);
	count = NULL;
}